#include <glib.h>

#define	C2P(c)		((gpointer) ((long) (c)))
#define	P2C(p)		((gchar) ((gintptr) (p)))

static gboolean node_build_string (GNode *node, gpointer data)
{
    gchar **p = data;
    gchar *string;
    gchar c[2] = "_";

    c[0] = ((gchar) ((gintptr) (node->data)));

    string = g_strconcat (*p ? *p : "", c, NULL);
    g_free (*p);
    *p = string;

    return FALSE;
}

static void glib_node_basic_test (void)
{
    GNode *root;
    GNode *node;
    GNode *node_B;
    GNode *node_F;
    GNode *node_G;
    GNode *node_J;
    guint i;
    gchar *tstring, *cstring;

    root = g_node_new (C2P ('A'));
    g_assert (g_node_depth (root) == 1 && g_node_max_height (root) == 1);

    node_B = g_node_new (C2P ('B'));
    g_node_append (root, node_B);
    g_assert (root->children == node_B);

    g_node_append_data (node_B, C2P ('E'));
    g_node_prepend_data (node_B, C2P ('C'));
    g_node_insert (node_B, 1, g_node_new (C2P ('D')));

    node_F = g_node_new (C2P ('F'));
    g_node_append (root, node_F);
    g_assert (root->children->next == node_F);

    node_G = g_node_new (C2P ('G'));
    g_node_append (node_F, node_G);
    node_J = g_node_new (C2P ('J'));
    g_node_prepend (node_G, node_J);
    g_node_insert (node_G, 42, g_node_new (C2P ('K')));
    g_node_insert_data (node_G, 0, C2P ('H'));
    g_node_insert (node_G, 1, g_node_new (C2P ('I')));

    g_assert (g_node_depth (root) == 1);
    g_assert (g_node_max_height (root) == 4);
    g_assert (g_node_depth (node_G->children->next) == 4);
    g_assert (g_node_n_nodes (root, G_TRAVERSE_LEAFS) == 7);
    g_assert (g_node_n_nodes (root, G_TRAVERSE_NON_LEAFS) == 4);
    g_assert (g_node_n_nodes (root, G_TRAVERSE_ALL) == 11);
    g_assert (g_node_max_height (node_F) == 3);
    g_assert (g_node_n_children (node_G) == 4);
    g_assert (g_node_find_child (root, G_TRAVERSE_ALL, C2P ('F')) == node_F);
    g_assert (g_node_find (root, G_LEVEL_ORDER, G_TRAVERSE_NON_LEAFS, C2P ('I')) == NULL);
    g_assert (g_node_find (root, G_IN_ORDER, G_TRAVERSE_LEAFS, C2P ('J')) == node_J);

    for (i = 0; i < g_node_n_children (node_B); i++)
    {
    node = g_node_nth_child (node_B, i);
    g_assert (P2C (node->data) == ('C' + i));
    }

    for (i = 0; i < g_node_n_children (node_G); i++)
    g_assert (g_node_child_position (node_G, g_node_nth_child (node_G, i)) == i);

    /* we have built:                    A
    *                                 /   \
    *                               B       F
    *                             / | \       \
    *                           C   D   E       G
    *                                         / /\ \
    *                                       H  I  J  K
    *
    * for in-order traversal, 'G' is considered to be the "left"
    * child of 'F', which will cause 'F' to be the last node visited.
    */

    tstring = NULL;
    g_node_traverse (root, G_PRE_ORDER, G_TRAVERSE_ALL, -1, node_build_string, &tstring);
    g_assert_cmpstr (tstring, ==, "ABCDEFGHIJK");
    g_free (tstring); tstring = NULL;
    g_node_traverse (root, G_POST_ORDER, G_TRAVERSE_ALL, -1, node_build_string, &tstring);
    g_assert_cmpstr (tstring, ==, "CDEBHIJKGFA");
    g_free (tstring); tstring = NULL;
    g_node_traverse (root, G_IN_ORDER, G_TRAVERSE_ALL, -1, node_build_string, &tstring);
    g_assert_cmpstr (tstring, ==, "CBDEAHGIJKF");
    g_free (tstring); tstring = NULL;
    g_node_traverse (root, G_LEVEL_ORDER, G_TRAVERSE_ALL, -1, node_build_string, &tstring);
    g_assert_cmpstr (tstring, ==, "ABFCDEGHIJK");
    g_free (tstring); tstring = NULL;

    g_node_traverse (root, G_LEVEL_ORDER, G_TRAVERSE_LEAFS, -1, node_build_string, &tstring);
    g_assert_cmpstr (tstring, ==, "CDEHIJK");
    g_free (tstring); tstring = NULL;
    g_node_traverse (root, G_PRE_ORDER, G_TRAVERSE_NON_LEAFS, -1, node_build_string, &tstring);
    g_assert_cmpstr (tstring, ==, "ABFG");
    g_free (tstring); tstring = NULL;

    g_node_reverse_children (node_B);
    g_node_reverse_children (node_G);

    g_node_traverse (root, G_LEVEL_ORDER, G_TRAVERSE_ALL, -1, node_build_string, &tstring);
    g_assert_cmpstr (tstring, ==, "ABFEDCGKJIH");
    g_free (tstring); tstring = NULL;

    cstring = NULL;
    node = g_node_copy (root);
    g_assert (g_node_n_nodes (root, G_TRAVERSE_ALL) == g_node_n_nodes (node, G_TRAVERSE_ALL));
    g_assert (g_node_max_height (root) == g_node_max_height (node));
    g_node_traverse (root, G_IN_ORDER, G_TRAVERSE_ALL, -1, node_build_string, &tstring);
    g_node_traverse (node, G_IN_ORDER, G_TRAVERSE_ALL, -1, node_build_string, &cstring);
    g_assert_cmpstr (tstring, ==, cstring);
    g_free (tstring); tstring = NULL;
    g_free (cstring); cstring = NULL;
    g_node_destroy (node);

    g_node_destroy (root);

    /* allocation tests */

    root = g_node_new (NULL);
    node = root;

    for (i = 0; i < 2048; i++)
    {
        g_node_append (node, g_node_new (NULL));
        if ((i%5) == 4) {
            node = node->children->next;
        }
    }
    g_assert (g_node_max_height (root) > 100);
    g_assert (g_node_n_nodes (root, G_TRAVERSE_ALL) == 1 + 2048);

    g_node_destroy (root);

}

gint main(gint argc, gchar **argv)
{
    glib_node_basic_test();

    return 0;
}
